Zkouškové příklady 36PAR
=Body: 1= Common CRCW a Arbitrary CRCW. Ktery je silnejsi a proc? Řešení Lemma 2. PRIORITY (prioritní) > ARBITRARY (náhodný) > COMMON (shodný) > CREW > EREW. Arbitrary je silnější než Common, protože algoritmy, které předpokládají, že počítač dovolí zapsat jen pokud jsou všechny hodnoty stejné (jinak končí v nedefinovaném stavu -> programátor nesmí dovolit aby došlo k zápisu do jedné buňky sdílené paměti pokud různé hodnoty) tak ve stejném čase a bez jakékoli změny budou tyto algoritmy fungovat na systému který zapíše náhodně vybranou hodnotu. Opačně to fungovat nebude a kdybychom chtěli spustit algoritmus napsaný pro Arbitrary na Common, museli bychom již provádět simulaci silnějšího na slabším. =Bodů: 2= Výpočet pořadí od konce v zřetězeném seznamu na CREW Zadání Popište časově optimální paralelní algoritmus pro výpočet pořadí od konce (rank) prvků ve zřetězeném seznamu o velikosti n na počítači CREW PRAM s n procesory. Vstupem algoritmu je zřetězený seznam ve sdílené paměti PRAM reprezentován pomocí pole následníků S\dots ,n . Řešení Přeskok ukazatelů, viz. slajd =Bodů: 3= PRAM post order cislovani stromu Zadání: *napsat (optimální?) algoritmus * p < n, T(n,p) Řešení 1) Mám seznam uzlů a seznam hran. Převedu na oboustranně orientovaný graf, označím si dopředné a zpětné hrany O(n/p), přidám hodnocení hran. 2) Vytvořím Eulerovu kružnici (skripta 108), O(n/p) 3) Vytvořím Eulerovu cestu - rozpojím kružnici v počátku O(1) 4) Zpětné hrany ohodnotím 1, dopředné 0. 5) Aplikuji PPS na vytvořené pole. 6) Ohodnocení uzlu=ohodnocení hrany z něj vedoucí PRAM, procesory s nezavislou pam a arit. jednotkou Zadání Popsat APRAM NC alg. pro paralel. prefix. soucet n cisel pomoci binarni asociativni operace *, T, C a psicka? Řešení pokud ho máš, tak sem s ním! Simulace Prioritni-CRCW na EREW Zadání Popiste a vysvetlete polylogaritmicky slozitou simulaci jednoho kroku Prioritni-CRCW-PRAM(n,p) algoritmu S na EREW-PRAM(n+O(p),) pocitaci. Predpokladejte jednotkovy casovy model, kdy R, W a L trvaji cas 1. Řešení viz slajdy 20-26. Algoritmus vypoctu hloubky uzlu na EREW PRAM Zadání Popiste EREW PRAM alg. pro vypocet hloubky uzlu eulerovskeho stromu T o n uzlech, kdy koren ma hloubku 0. Vysledkem bude pole Level1,...,n. Eulerovsky strom T ma m = 2n-2 hran a je reprezentovan polem uzlu, ktere maji odkazy na cyklicke seznamy svych hran. Predpokladejte, ze jiz je zkonstruovana eulerovska cesta vznikla pri pruchodu T do hloubky a je ulozena v poli EA1,...,m, kde EAi je i-ta hrana teto cesty. Odvodte paralelni cas T(n,p), jestlize lokalni operace L i globalni R/W trvaji cas 1. Řešení Ze zadani vyplyva, ze mame jiz vytvorene pole nasledniku a z nich ziskane informace o rank (poradi) jednotlivych hran. Tato informace (rank) je ulozena pro kazdou hranu v Eulerovske ceste vznikle rozseknutim Eulerovske kruznice. 1) Zjisteni orientace hran (Kazdy CPU nad kazdou hranou se podiva na antiparalelni dvojce a podle hodnoty rank se urci smer hrany) 2) Kazde dopredne hrane se nastavi priznak na 1, zpetne hrane na -1 3) Pomoci PPS se provede soucet a kazdy bude mit nastavenou hodnotu urovne ve stromu =Bodů: 4= urcete p' a t' u PRAMu (m,p') Zadání Odvodte pocet procesoru p‘ a casovou slozitost t‘ simulace PRAM(n,p) algoritmu s casem t = T(n,p) na PRAM (m,p‘) pocitaci tehoz typu, je-li m < n. Tuto simulaci popiste. Jake dalsi predpoklady jsou treba? Uvazujte jednotkovy casovy model, kdy operace R,W a L trvaji cas 1. Řešení viz predmaska 3/slajd 19 Určení pořadí v řetězeném seznamu pro PRAM Zadání alg. pro urceni poradi v zretezenem seznamu pro EREW-PRAM s p=n, jakou ma skalovatelnost? napiste alg. pro p\rho _{XXX} a a komunikační zpoždění \tau _{XXX} pro danou operaci XXX na síti s červím přepínáním (WH). Zdrojový uzel vysílá packet o velikosti m. Přenos packetu o velikosti μ na vzdálenost d trvá čas t(d,\mu) = t_s + d t_d + \mu t_m Popište co nejefektivnější algoritmus. Odvodte co nejpresneji pocet kroku r_ {XXX} a komunikacni zpozdeni t_{XXX} a porovnanim se spodnimi mezemi XXX urcete optimalni algoritmus. OAS * T(Z,Z), vseportovy, WH * Kombinujici 2-portovy 2D toroid K(z1,z2) s WH prepinanim. Zdroj uzel a1,a2, 0<= a1 < z1 a pro kazdy uzel ma pripraveny paket o velikosti m. (zde je ještě potřeba spočítat paralelní součet délek použitých cest g_{OAS} a jeho spodní mez \gamma_{OAS} ) * 1-port WH 2D mrizka M(z1, z2), zdroj vysilani na a2 ma pro kazdy uzel pripravenu zpravu o velikosti M. AAS * Qn ** Nekombinující, nebo v případě že t_s \ll /mu t_m použít nekombinující algoritmus (skripta 190) ** Pro případ že t_s \ge /mu t_m v kombinující síti použít standartní výměnu (SV) ze str. 187 * 1-portová mřížka M(\sqrt{p},\sqrt{p}) ** Slidy 11/26 ** kvadrantová výměna (skripta 189) ** binární výměna (skripta 189) OAB * 2 portová 2D mřížka M(z1,z2) * 2 portová 1D mřížka * všeportový 2D toroid ** zde je ještě potřeba spočítat paralelní součet délek použitých cest g_{OAS} a jeho spodní mez \gamma_{OAS} ** zobecněná diagonála, viz skripta str. 177 cenove optimalni APRAM alg. pro paralelni redukci Zadání Standartni model APRAM (lokalni operace trvaji cas 1, k>=1 krat za sebou jdouci R/W trva k+d-1; a barierova synchronizace B(p)=\alpha d \log{p} , kde \alpha a d > 1) ma nezavislou pametovou a vypocetni jednotku. Popiste cenove optimalni APRAM alg. pro paralelni redukci n cisel pomoci binarni asociativni operace @ (puntik ;-). Odvodte T(n,p), C(n,p), \psi _1(p) , \psi _2(n) . Analyzu casove slozitosti provedte pro model dynamicke barierove synchronizace. Řešení Řešení je popsané podrobně na stránkách předmětu, zde je výtah: Postup A Pro efektivní simulaci PRAM algoritmu s p_p procesory na APRAM počítači je potřeba řádově snížit počet procesorů z p_a na p'_a = \tfrac{p_p}{B(p_p)} . Víme, že p-procesorový PRAM algoritmus pro paralelní redukci nad polem n'' hodnotje časově i cenově optimální, pokud p = \Theta (\tfrac{n}{\log{n}}) . Položme pro jednoduchost p_p = \tfrac{n}{\log{n}} . Pro optimální počet procesorů p'_a pro APRAM redukci platí: p'_a = \dfrac{p_p}{B(p_p)} = \cfrac{\tfrac{n}{\log{n}}}{\alpha d \log{(\tfrac{n}{\log{n}})}} = \dfrac{n}{\alpha d \log{n} (\log{n} - \log{\log{n}})} \dot= \dfrac{n}{\alpha d \log^2{n}} V první fázi výpočtu každý APRAM procesor zredkuje sekvence n/p'_a = \alpha d \log^2{n} = \beta čísel. Z předpokladu pro nezávislou pamětovou a aritmetickou jednotku plyne, že zatímco se z paměti pomocí R načítají hodnoty, aritmetická jednotka je okamžitě redukuje na mezivýsledky. Pak je složitost první fáze rovna T_a^I(n,p'_a ) = d+ \beta - 1 + 1 \dot= \beta . Druhá fáze začíná bariérou, pak se zapíšou lokální výsledky první fáze, znovu bariéra a pak se provede APRAM redukce p'_a čísel na p'_a procesorech: T_a^{II}(n,p'_a ) \dot= B(p'_a) + d + B(p'_a) + 2B(p'_a)\log{p'_a} \dot= 2B(p'_a)\log{p'_a} \le 2 \beta . ''pozn. - podle mého by tam mělo ještě někde být d... Výraz 2B(p'_a)\log{p'_a} předpokládá, že se v každém kroku účastní všech p'_a procesorů. Při dynamické bariérové synchronizaci ale počet procesorů exponenciálne klesá, takže čas spotřenovaný na dynamickou bariérovou synchronizaci je t_{BS} = 2( B(p'_a) + B(\dfrac{p'_a}{2}) + B(\dfrac{p'_a}{2^2}) + \cdots + B(2)) t_{BS} = \alpha d \log{p'_a}(log{p'_a}+1) \dot= \alpha d \log^2{p'_a} \le \beta Celkový čas je T_a(n, p'_a) = T_a^{I}(n,p'_a ) + T_a^{II}(n,p'_a ) \le 2 \beta . Celková cena je C_a(n, p'_a) = p'_a T_a(n, p'_a) = \dfrac{n}{\beta} \times 2\beta = 2n Postup B Sekvence APRAM redukce n čísel na p_a procesorech je \left \langle R \left \langle RL \right \rangle ^{\tfrac{n}{p_a}-1} B W B \left \langle R R L B W B \right \rangle ^{\log{p_a}} \right \rangle T_a(n,p_a) = d + \left ( \frac{n}{p_a} - 1 \right ) + 1 + B(p_a) + \log{p_a}(d + 1 + 1 + B(p_a) + d + B(p_a)) Po sečtení, zaokrouhlení a započtení dynamické bariérové synchronizace (viz předchozí)dostáváme T_a(n,p_a) = \frac{n}{p_a} + 2 d \log{p_a} + 2B(p_a)\log{p_a} \dot= \frac{n}{p_a} + \alpha d \log^2{p_a} C_a(n,p_a) = n + \alpha d p_a \log^2{p_a} Protože SU(n) \dot= n má rovnice E(n,p_a) = \tfrac{n}{n + \alpha d p_a \log^2{p_a}} = E_0 řešení: n = \frac{E_0 \alpha d}{1 - E_0} p_a \log^2{p_a} a p_a \dot= \frac{\gamma n}{\log^2{\gamma n}} , kde \gamma = \frac{1 - E_0}{E_0 \alpha d} Paralelní prefixový součet (PPS) APRAM Melo to byt pro p < n procesoru, takze vlastni vypocet slozitosti mel sekvencni a paralelni cast. Ta paralelni pak vypadala \langle RRLBWB\rangle ^{\log{p}} . Z toho zjistit T(n,p) dosazenim za R,L,W,B, vypocitat C(n,p), Psi1, Psi2. Poznámka APRAM pocitac postupuje stejne jako PRAM pocitac, akorat se musi prokladat barierama Ostatní modely T, E , ψ1, ψ2, ψ3, Tmin * 2D toroid * Qn ( n = \log{p} ), WH přepínání. **algoritmus se zelenými a žlutými registry * škálovatelnost v (hyperkub.?) síti v případě že každý procesor má n/p hodnot (možná je to dohromady s předchozím zadáním) Lineární algebra LU dekompozice Jakobi Sudo lichá redukce Třídění / řazení 3D sort Quicksort Bitonic mergesort (BMS) Snakelike řazení Odvoďte výraz pro netriviální spodní mez na počet kroků hadovitého (snake-like) paralelního řazení n^2 čísel pomocí operace Porovnej&Vyměn (CE) na 2-D mřížce M(n,n) . Shearsort Matice Cannonův algoritmus násobení matic Foxův algoritmus násobení matic (BMR) Popište a vysvětlete Foxův algoritmus paralelního násobení čtvercových \sqrt{N} \times \sqrt{N} matic C = AB na vše-portové hyperkrychli Q_{\log{p}} procesorů, kde p < N . Odvoďte co nejpřesnější výraz pro paralelní čas T(N,p) , jestliže # směrovače provádění červí (WH) prepínání packetů, kde přenos packetu o velikosti μ'' mezi 2 uzly ve vzdálenosti ''d trvá t(d,\mu) = t_s + d t_d + \mu t_m # prvky matic mají velikost m'' a # '''sekvenční' lokální nasobení dvou matic o velikosti r \times r trvá čas \alpha r^3 , kde m'' a ''α jsou konstanty. Pro zadanou efektivnost E''0 odvoďte izoefektivní funkce \psi_1(p) a \psi_2(N) . Odvoďte '''minimální čas' a spodní mez počtu procesorů \psi_3(N) pro dosažení asymptoticky minimálního času. Násobení matice x vektor Ostatní * na oBFn dokazte, ze pro dane vstupy a1..an kde a1<..